esamedistatoingegneriafandomcom_it-20200215-history
Settore Informazione-Sezione B-I Prova-Informatica
Il candidato illustri analogie e differenze della programmazione ad oggetti rispetto alla programmazione strutturata. Opzionalmente, ne discuta i vantaggi in termini di maggiore ingegnerizzazione ottenibile in fase di modellazione di un sistema software. Bis - Il candidato introduca la programmazione ad oggetti e ne discuta i principali aspetti caratterizzanti. Questa domanda è apparsa anche nella sezione A. La risposta può essere trovata qui ---- Un qualsiasi linguaggio di programmazione mette a disposizione dell’utente dei costrutti linguistici, come typedef in C o class in Java, che permettono di progettare e realizzare nuovi tipi di dati (Tipi di Dato Astratto), con particolare riferimento alle strutture dati. Il candidato, facendo riferimento ad un linguaggio fra quelli di sua conoscenza, discuta vantaggi e svantaggi di tali strutture dati aiutandosi, eventualmente, con opportuni esempi. ---- Il candidato spieghi le principali differenze tra un sistema puramente combinatorio ed uno sequenziale, facendo riferimento ad alcuni opportuni esempi. In un sistema puramente combinatorio l'uscita in un dato istante di tempo è funzione solamente dagli ingressi in quel determinato istante, e tale relazione è descritta da una funzione logica (vengono detti circuiti senza memoria). Un esempio di circuiti combinatori sono le porte logiche, queste realizzano funzioni logiche dando in uscita vero , 1, o falso, 0, a seconda delle combinazioni degli ingressi. L'operazione AND dà come valore 1 se tutti gli operandi hanno valore 1, mentre restituisce 0 in tutti gli altri casi. Tale operazione è anche detta prodotto logico. A B A AND B 0 0 0 0 1 0 1 0 0 1 1 1 È possibile realizzare un'operazione logica AND con un numero di proposizioni arbitrarie concatenando varie AND a due ingressi, per esempio: p1 AND (p2 AND (p3 AND p4)) Nei circuiti digitali, la porta logica AND è un meccanismo comune per avere un segnale di vero se un certo numero di altri segnali sono tutti veri. Nella teoria degli insiemi corrisponde all'intersezione. Il simbolo di una porta AND è: Un circuito sequenziale è un circuito logico in cui le uscite all'istante t non dipendono solo dagli ingressi nel medesimo istante, ma anche dai valori assunti in precedenza: si tratta ovvero di un sistema dinamico dotato di memoria. un esempio di circuiti sequenziali sono i flip flop: circuiti elettronici bistabili molto semplici, utilizzati nell'elettronica digitale come dispositivi di memoria elementare. Il flip-flop SR è il più semplice dal punto di vista circuitale e fu anche il primo ad essere realizzato. Ha due ingressi s (Set) e r (Reset, detto anche Clear) e due uscite q e q_n. È una rete sequenziale asincrona (senza clock) che si evolve in accordo alle seguenti specifiche: quando lo stato d'ingresso è s=1 e r=0 il flip-flop si setta, cioè porta a 1 il valore della variabile d'uscita q e a 0 la variabile d'uscita q_; quando lo stato d'ingresso è s=0 e r=1 il flip-flop si resetta cioè porta a 0 il valore della variabile d'uscita q e a 1 la variabile d'uscita q_; quando lo stato d'ingresso è s=0 e r=0 il flip-flop conserva, cioè mantiene inalterato il valore di entrambe le variabili d'uscita. Quando entrambi i valori R e S sono bassi, il flip-flop si trova nello stato neutro e mantiene il valore delle uscite, in questo caso si dice che "fa memoria" (mantiene cioè in uscita il dato precedente memorizzato). Quando invece entrambi gli ingressi hanno valore 1, si ha una condizione logicamente non definita. Elettronicamente, con gli ingressi S e R contemporaneamente a 1, il circuito del flip-flop SR si trasforma in un oscillatore astabile la cui frequenza dipende dal ritardo di trasmissione delle porte logiche componenti; le uscite del flip-flop SR emettono allora due onde quadre di pari frequenza e sfasate di 180°. Questa "perdita di senso logico" che è possibile nei flip-flop SR è il motivo principale per cui, di norma, si impiegano flip-flop JK o D nei circuiti digitali. Tabella di verità (Q(t+1) e Q_n(t+1) (uscita negata) indicano gli stati futuri della memoria all'istante t+1 in base agli ingressi all'istante t): S R Q(t+1) Q_n(t+1) Descrizione 0 0 Q(t) Qn(t) memoria 0 1 0 1 reset 1 0 1 0 set 1 1 ? ? uscite non definite ---- Spesso un problema può essere risolto adottando, indifferentemente, una soluzione basata su approccio iterativo o una basata su approccio ricorsivo. Il candidato illustri queste due tecniche risolutive attraverso un esempio e evidenzi, brevemente, pregi e difetti di entrambe. Bis - Si descrivano le differenze fra ricorsione e iterazione. *Viene detto algoritmo ricorsivo un algoritmo espresso in termini di se stesso, ovvero in cui l'esecuzione dell'algoritmo su un insieme di dati comporta la semplificazione o suddivisione dell'insieme di dati e l'applicazione dello stesso algoritmo agli insiemi di dati semplificati. Questo tipo di algoritmo risulta particolarmente utile per eseguire dei compiti ripetitivi su di un set di input variabili. L'algoritmo richiama se stesso generando una sequenza di chiamate che ha termine al verificarsi di una condizione particolare che viene chiamata condizione di terminazione, che in genere si ha con particolari valori di input. La tecnica ricorsiva permette di scrivere algoritmi eleganti e sintetici per molti tipi di problemi comuni, anche se non sempre le soluzioni ricorsive sono le più efficenti. Questo è dovuto al fatto che comunemente la ricorsione viene implementata utilizzando le funzioni, e che l'invocazione di una funzione ha un costo rilevante, e questo rende più efficenti gli algoritmi iterativi. Un esempio di tipo matematico, il calcolo del fattoriale di un numero n: Chiameremo fattoriale di n e scriveremo n!, il prodotto dei primi n numeri naturali, ottenuto come segue: 0! = 1; n! = 1 * 2 * 3 * ...... * n-1 * n; per n > 0. Rielaborando la definizione, ci si accorge di come sia possibile darne una versione ricorsiva. Sia a tal proposito: n! = (1 * 2 * 3 * ...... * n-1) * n; si ottiene, n! = (n-1)! * n; da cui, iterando, n! = (n-2)! * n-1 * n continuando ad iterare la definizione, arriveremo alle condizioni di terminazione, per cui il risultato cercato è noto: 0! = 1! = 1 Siamo adesso in grado di dare un algoritmo ricorsivo che chiameremo FATT, per il calcolo del fattoriale: FATT(n) if n 0 or n 1 return 1 else return n*FATT(n-1) Quando l'algoritmo viene eseguito la prima volta, il valore di n viene confrontato con 0 e con 1, nel caso in cui il valore sia diverso, la procedura viene chiamata ricorsivamente su valori più piccoli sino a quando n non risulta uguale ad 1, nel qual caso il risultato è noto e può essere restituito dalla funzione attuale a quella che l'aveva in precedenza chiamata. I risultati restituiti da ognuna delle procedure ricorsive vengono di volta in volta moltiplicati. Il penultimo valore restituito sarà proprio uguale ad (n-1)!, quest'ultimo verrà moltiplicato per n e l'algoritmo potrà restituire il risultato cercato. *Dicesi algoritmo iterativo un algoritmo costituito da una sequenza di azioni che viene ripetuta, finché è necessaria la ripetizione stessa (un ciclo). Tutte le operazioni che richiedono la ripetizione di una stessa azione più volte, ma in numero finito sono dette procedure iterative. Ad ogni iterazione, l'esecutore svolge un compito. Al termine verifica se tale compito vada ripetuto mediante una condizione di ripetizione. Per rendere agevole l'implementazione di procedure iterative nei linguaggi di programmazione di alto livello, sono disponibili due fondamentali costrutti: for e while. Il primo si presta ai cicli enumerativi (ossia quelli in cui il numero di iterazioni è prestabilito o dipende da un valore numerico calcolato prima dell'iterazione), mentre il secondo permette una libera applicazione della condizione di iterazione. Ad esempio il fattoriale precedentemente espresso in modo ricorsivo può essere espresso in modo iterativo secondo l'algoritmo: FATTiterativo (n) fatt = 1 while (1 <= n) fatt = fatt * n n - 1 return fatt ---- Il candidato risponda al seguente quesito: qual è il ruolo dell’unità di controllo di un calcolatore? Durante l’esecuzione di una singola istruzione quali sono le attività di sua competenza? Quali altre componenti del calcolatore vengono coinvolte? La CPU, o central processing unit, è la parte più importante del computer infatti dirige e controla ogni sua attività, coordinando le atttività di ogni altra unità (memorie e periferiche) ed eseguendo le istruzioni dei programmi. E' costituita di: *CU: unità di controllo che legge dalla memoria le istruzioni, e nel caso occorra anche i dati per eseguire l'istruzione letta, esegue le istruzioni e memorizza il sisultato scrivendolo in memoria o in un registro d'accumulazione. *ALU:unità aritmetico logica, esegue le operazioni logiche e aritmetiche. *Registri: speciali locazioni di memoria interna alla CPU, a cui è possibile accedere rapidamente ---- Il candidato risponda al seguente quesito: un’azienda vuole codificare i propri prodotti secondo un codice binario a N bit. Il numero di articoli diversi gestiti dall’azienda può variare tra 1200 e 2000. Qual è il numero minimo di bit (N) richiesto per codificare tutti gli articoli? Perché? N=\log_2{2000}=10.9658 dato il risultato ed essendovi un vincolo di interezza del numero di bit otteniamo N=11. ---- Il candidato descriva i ruoli tipici di compilatori ed interpreti dei moderni linguaggi di programmazione, mettendone in evidenza le differenze e discutendone eventuali vantaggi e svantaggi. I programmi scritti nei linguaggi di programmazione di alto livello, quelli più vicini all'uomo che alla macchina, possono essere tradotti nel linguaggio macchina in due modi distinti, che presentano entrambi vantaggi e svantaggi. *Gli interpreti ''operano traducendo una riga del programma per volta, ed eseguendola immediatamente. *I' compilatori ''traducono per intero il programma prima di eseguirlo. Interpreti e compilatori sono a loro volta dei programmi, che spesso sono scritti nel linguaggio che essi stessi traducono. I linguaggi di programmazione che richiedono un interprete sono definiti ''linguaggi interpretati, ''mentre quelli che richiedono un compilatore sono chiamati ''linguaggi compilati. ''Entrambi presentano vantaggi e svantaggi, descritti nel seguito. ''Vantaggi e svantaggi dei linguaggi interpretati I linguaggi di programmazione che lavorano con un interprete risultano solitamente più lenti, poiché la traduzione riga per riga deve essere effettuata ogni volta che si vuole eseguire il programma. Inoltre l'interprete deve essere sempre disponibile nel momento dell'esecuzione del programma, e questo risulta scomodo per chi desidera distribuire i propri programmi ad altri.Tra l'altro, il fatto che l'esecuzione del programma richieda la 'contemporanea disponibilità dei file sorgenti e dell'interprete, poiché la traduzione viene effettuata in tempo reale, comporta dei problemi di riservatezza per chi commercializza le proprie applicazioni: l'utente riceve anche una copia dei file sorgenti, che può modificare come preferisce. D'altra parte, agli sviluppatori i linguaggi interpretati offrono il vantaggio di poter apportare delle modifiche al programma in modo molto più semplice e immediato, e inoltre il controllo sulla validità delle istruzioni eseguito riga per riga evidenzia immediatamente eventuali errori commessi. ''Vantaggi e svantaggi dei linguaggi compilati I linguaggi di programmazione che utilizzano un compilatore offrono notevoli vantaggi rispetto a quelli interpretati. I programmi scritti in questi linguaggi risultano molto più veloci, poiché la traduzione viene effettuata una volta per tutte, mentre poi viene eseguito direttamente il file eseguibile, ovvero il file contenente i codici in linguaggio macchina che sono riconosciuti direttamente dal computer. Inoltre, l'esecuzione del programma non richiede né la disponibilità dei file sorgenti, né quella dell'interprete, perciò risulta molto più semplice distribuire le applicazioni, senza alcun problema legato alla riservatezza del proprio lavoro: l'utente non ha alcuna possibilità di modificare il lavoro svolto dal programmatore. Anche i compilatori presentano tuttavia alcuni svantaggi: poiché l'esecuzione del programma richiede la preventiva traduzione dei file sorgenti per creare i file eseguibili, anche la più piccola modifica apportata al codice sorgente obbliga a una nuova traduzione dell'intero programma, che richiede un certo tempo. Inoltre, il fatto che la traduzione venga sempre eseguita per intero comporta l'impossibilità di controllare immediatamente la validità delle istruzioni immesse. In ogni caso, quasi tutte le applicazioni commerciali oggi disponibili sono scritte utilizzando linguaggi compilati, mentre i linguaggi interpretati vengono utilizzati quasi esclusivamente per scopi particolari o in fase di prova. ----